1565. Play with floor and ceil

 

Theorem. For any two integers x and k there exists two more integers p and q such that

x = p + q

It’s a fairly easy task to prove this theorem, so we’d not ask you to do that. We’d ask for something even easier! Given the values of x and \, you’d only need to find integers p and q that satisfies the given equation.

 

Input. The first line contains the number of test cases t (1 ≤ t ≤ 1000). In each of the following t lines you’d be given two positive integers x and k. You can assume that x and k will always be less than 108.

 

Output. For each test cases print in one line two integers p and q. If there are multiple pairs of p and q that satisfy the equation, any one would do. But to help us keep our task simple, please make sure that the values p and q fit in a 64 bit signed integer.

 

Sample input

Sample output

3

5 2

40 2

24444 6

1 1

1 1

0 6

 

 

SOLUTION

Extended Euclidean algorithm

 

Algorithm analysis

If x is divisible by k, then  =  = x / k. Choosing p = 0, q = k, we get: 0 * (x / k) + k * (x / k) = x.

Let x is not divisible by k. If n = , then m =  = n + 1. Since GCD(n , m) = GCD(n , n + 1) = 1, then based on the extended Euclidean algorithm, there exist integers t and u such that 1 = tn + um. Multiplying the equality by x, we get x = xtn + xum, wherefrom p = xt, q = xu.

 

Example

In the first test case x = 5, k = 2. The value of x is not divisible by k. Compute n =  = 2, m =  = 3. The solution to the equation 2t + 3u = 1 is the pair (t, u) = (-1, 1). Multiply the equation by x = 5. The solution to the equation 2p + 3q = 5 is the pair (p, q) = (5t, 5u) = (-5, 5). The next relation holds:

5 = (-5) *  + 5 *  = (-5) * 2 + 5 * 3 = -10 + 15

 

Algorithm realization

During the calculations we’ll use a 64-bit long long integer type. To make the code easier, let’s override the type:

 

typedef long long i64;

 

Function gcdext represents an extended Euclidean algorithm.

 

void gcdext(i64 a,i64 b, i64 *d, i64 *x, i64 *y)

{

  i64 s;

  if (b == 0)

  {

    *d = a; *x = 1; *y = 0;

    return;

  }

  gcdext(b,a % b,d,x,y);

  s = *y;

  *y = *x - (a / b) * (*y);

  *x = s;

}

 

The main part of the program. Read the number of tests. For each test case read the values x and k.

 

scanf("%d",&tests);

while(tests--)

{

  scanf("%lld %lld",&x,&k);

 

If x is divisible by k, set p = 0, q = k.

 

  if (x % k == 0) { p = 0; q = k;}

  else

  {

 

Otherwise compute n =  è m =  and run the extended Euclidean algorithm. It finds such values of t and u that 1 = tn + um. Next we find p = xt, q = xu and print the answer.

 

    n = (int)floor(1.0 * x / k); m = (int)ceil(1.0 * x / k);

    gcdext(n,m,&g,&t,&u);

    p = t * x; q = u * x;

  }

  printf("%lld %lld\n",p,q);

}